Privacy%2DPreserving Data Publishing An Overview

Competitive Privacy Secure Analysis on Integrated Sequence Data.
Abstract. Sequence data analysis has been extensively studied in the literature. However, most previous work focuses on analyzing sequence data from a single source or party. In many applications such as logistics and network traffic analysis, sequence data comes from more than one source or party. When multiple autonomous organizations collaborate and integrate their sequence data to perform analysis, sensitive business information of individual parties can be easily leaked to the other parties. In this paper, we propose the notion of competitive privacy to model the privacy that should be protected when carrying out data analysis on integrated sequence data. We propose a query restriction algorithm that can reject malicious queries with low auditing overhead. Experimental results show that our proposed method guarantees the protection of competitive privacy with only a significantly small portion of queries being restricted. 1
Global privacy guarantee in serial data publishing.
Abstract — While previous works on privacy-preserving serial data publishing consider the scenario where sensitive values may persist over multiple data releases, we find that no previous work has sufficient protection provided for sensitive values that can change over time, which should be the more common case. In this work, we propose to study the privacy guarantee for such transient sensitive values, which we call the global guarantee. We formally define the problem for achieving this guarantee. We show that the data satisfying the global guarantee also satisfies a privacy guarantee commonly adopted in the privacy literature called the local guarantee. I.
Workshop Organizers%27 Message.

Finding the influence set through skylines.
Given a set P of products, a set O of customers, and a product p ∈ P, a bichromatic reverse skyline query retrieves all the customers in O that do not find any other product in P to be absolutely better than p. More specifically, a customer o ∈ O is in the reverse skyline of p ∈ P if and only no other product in P better matches the preference of o on all dimensions. The only existing bichromatic reverse skyline algorithm, which we refer to as basic, is designed for uncertain data. This paper focuses on traditional datasets, where each object is a precise point. Since a precise point can be regarded as a special uncertain object, basic can still be applied. However, as precise data are inherently easier to handle than uncertain data, one should expect that basic can be further improved by taking advantage of the reduced problem complexity. Indeed, we observe several non-trivial heuristics that can optimize the access order to achieve stronger pruning power. Motivated by this, we propose a new algorithm called BRS, and prove that BRS never entails more I/Os than basic. Besides our theoretical analysis, we also perform extensive experiments to show that in practice BRS usually outperforms basic by a large factor. For example, when both P and O follow the anti-correlated distribution, BRS is faster than basic by an order of magnitude. Finally, we address a new variation of bichromatic reverse skyline search where the conventional definition of dynamic skylines no longer makes sense. 1.
FF%2DAnonymity When Quasi%2Didentifiers Are Missing.
Abstract — Existing approaches on privacy-preserving data publishing rely on the assumption that data can be divided into quasi-identifier attributes (QI) and sensitive attribute (SA). This assumption does not hold when an attribute has both sensitive values and identifying values, which is typically the case. In this paper, we study how such attributes would impact the privacy model and data anonymization. We identify a new form of attacks, called ”freeform attacks”, that occur on such data without explicit QI attributes and SA attributes. We present a framework for modeling identifying/sensitive information at the value level, define a problem to eliminate freeform attacks, and outline an efficient solution. I.
Query by Humming.
This is taken from [SZ04, Chap. 6]. It is the second of three applications they develop based on their review of timeseries techniques in the first four chapters. 1. “Query by humming ” is a challenging unsolved problem in timeseries matching. Because matches cannot be exact, dynamic time warping (DTW) is needed but this is slow, even when we use dynamic programming (see timeseries.pdf, Note 7). Shasha and Zhu find an approximation which excludes false negatives (failed alarm) and speeds up the matching process substantially. The problem is to match, from a database of tunes, the tune that somebody hums, maybe quite inaccurately. The melodic contour approach (a melody is represented as a sequence of u,- and d as the pitch goes up, stays the same or goes down—or maybe, more refined, as U, u,-, d and D) discriminates only very poorly among the many possible entries in the database. It also requires the identification of individual notes from the hum-query, which is a difficult problem. (The database entries can be derived from the written score, which provides the individual notes, so there is no problem there.) So Shasha and Zhu represent the hum-query as a timeseries of pitches, sampled regularly, say every 10 ms, without concern about individual notes. They also store the scores in the database as timeseries of pitches. 2. Let’s start with a database entry, “Hey Jude ” (John Lennon, Paul McCartney, 1965) From the score we can extract the following sequence of (pitch,duration) pairs (60,4),(57,10),(57,2),(60,2),(62,2),(55,8),(-,4),(55,2),(57,2),
Anonymization%2Dbased attacks in privacy%2Dpreserving data publishing.
Data publishing generates much concern over the protection of individual privacy. Recent studies consider cases where the adversary may possess different kinds of knowledge about the data. In this article, we show that knowledge of the mechanism or algorithm of anonymization for data publication can also lead to extra information that assists the adversary and jeopardizes individual privacy. In particular, all known mechanisms try to minimize information loss and such an attempt provides a loophole for attacks. We call such an attack a minimality attack. In this article, we introduce a model called m-confidentiality which deals with minimality attacks, and propose a feasible solution. Our experiments show that minimality attacks are practical concerns on real datasets and that our algorithm can prevent such attacks with very little overhead and information loss. 
Preserving Individual Privacy in Serial Data Publishing

Can the Utility of Anonymized Data be used for Privacy Breaches%3F

Anonymization with Worst%2DCase Distribution%2DBased Background Knowledge

Online Skyline Analysis with Dynamic Preferences on Nominal Attributes.
Abstract—The importance of skyline analysis has been well recognized in multicriteria decision-making applications. All of the previous studies assume a fixed order on the attributes in question. However, in some applications, users may be interested in skylines with respect to various total or partial orders on nominal attributes. In this paper, we identify and tackle the problem of online skyline analysis with dynamic preferences on nominal attributes. We investigate how changes of orders in attributes lead to changes of skylines. We address two novel types of interesting queries: a viewpoint query returns with respect to which orders a point is (or is not) in the skylines, and a refined skyline query retrieves the skyline with respect to a specific order. We develop two methods systematically and report an extensive performance study using both synthetic and real data sets to verify the effectiveness and the efficiency of our methods. Index Terms—Skyline, materialization, data warehouses, preferences. Ç
%28alpha%2C k%29%2Danonymous data publishing.
E-mail address:
Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor.
Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs. Such a problem has many real life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, the fastest known method has exponential time complexity on the data size. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap. Extensive experiments are conducted to show that our algorithm is many times faster than the best-known technique. 1.
Creating Competitive Products.
The importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. Most previous works study how to help customers find a set of “best” possible products from a pool of given products. In this paper, we identify an interesting problem, creating competitive products, which has not been studied before. Given a set of products in the existing market, we want to study how to create a set of “best ” possible products such that the newly created products are not dominated by the products in the existing market. We refer such products as competitive products. A straightforward solution is to generate a set of all possible products and check for dominance relationships. However, the whole set is quite large. In this paper, we propose a solution to generate a subset of this set effectively. An extensive performance study using both synthetic and real datasets is reported to verify its effectiveness and efficiency. 1.
On the Capacity of Multi%2DChannel Wireless Networks Using Directional Antennas.

Anonymization by Local Recoding in Data with Attribute Hierarchical Taxonomies.
Abstract—Individual privacy will be at risk if a published data set is not properly deidentified. k-Anonymity is a major technique to deidentify a data set. Among a number of k-anonymization schemes, local recoding methods are promising for minimizing the distortion of a k-anonymity view. This paper addresses two major issues in local recoding k-anonymization in attribute hierarchical taxonomies. First, we define a proper distance metric to achieve local recoding generalization with small distortion. Second, we propose a means to control the inconsistency of attribute domains in a generalized view by local recoding. We show experimentally that our proposed local recoding method based on the proposed distance metric produces higher quality k-anonymity tables in three quality measures than a global recoding anonymization method, Incognito, and a multidimensional recoding anonymization method, Multi. The proposed inconsistency handling method is able to balance distortion and consistency of a generalized view. Index Terms—k-anonymization, local recoding, generalization distance, inconsistency. Ç
Efficient skyline querying with variable user preferences on nominal attributes.
Current skyline evaluation techniques assume a fixed ordering on the attributes. However, dynamic preferences on nominal attributes are more realistic in known applications. In order to generate online response for any such preference issued by a user, one obvious solution is to enumerate all possible preferences and materialize all results of these preferences. However, the pre-processing and storage requirements of a full materialization are typically prohibitive. Instead, we propose a semi-materialization method called the IPO-tree Search which stores partial useful results only. With these partial results, the result of each possible preference can be returned efficiently. We have also conducted experiments to show the efficiency of our proposed algorithm. 1.
Privacy preserving serial data publishing by role composition.
Previous works about privacy preserving serial data publishing on dynamic databases have relied on unrealistic assumptions of the nature of dynamic databases. In many applications, some sensitive values changes freely while others never change. For example, in medical applications, the disease attribute changes with time when patients recover from one disease and develop another disease. However, patients do not recover from some diseases such as HIV. We call such diseases permanent sensitive values. To the best of our knowledge, none of the existing solutions handle these realistic issues. We propose a novel anonymization approach called HD-composition to solve the above problems. Extensive experiments with real data confirm our theoretical results. 1.
Privacy preserving serial data publishing by role composition.
Previous works about privacy preserving serial data publishing on dynamic databases have relied on unrealistic assumptions of the nature of dynamic databases. In many applications, some sensitive values changes freely while others never change. For example, in medical applications, the disease attribute changes with time when patients recover from one disease and develop another disease. However, patients do not recover from some diseases such as HIV. We call such diseases permanent sensitive values. To the best of our knowledge, none of the existing solutions handle these realistic issues. We propose a novel anonymization approach called HD-composition to solve the above problems. Extensive experiments with real data confirm our theoretical results. 1.
Scaling and time warping in time series querying.

%28alpha%2C k%29%2Danonymity Based Privacy Preservation by Lossy Join.

Advanced Macro%2Dblock Entropy Coding in H.264.

Advanced Real%2Dtime Rate Control in H.264.

Mining favorable facets.

Minimality Attack in Privacy Preserving Data Publishing.
E-mail address:
On Efficient Spatial Matching.
E-mail address:
Efficient Skyline Querying with Variable User Preferences on Nominal Attributes
Current skyline evaluation techniques assume a fixed ordering on the attributes. However, dynamic preferences on nominal attributes are more realistic in known applications. In order to generate online response for any such preference issued by a user, one obvious solution is to enumerate all possible preferences and materialize all results of these preferences. However, the pre-processing and storage requirements of a full materialization are typically prohibitive. Instead, we propose a semi-materialization method called the IPO-tree Search which stores partial useful results only. With these partial results, the result of each possible preference can be returned efficiently. We have also conducted experiments to show the efficiency of our proposed algorithm. 1.
Achieving k%2DAnonymity by Clustering in Attribute Hierarchical Structures.
Abstract. Individual privacy will be at risk if a published data set is not properly deidentified. k-anonymity is a major technique to de-identify a data set. A more general view of k-anonymity is clustering with a constraint of the minimum number of objects in every cluster. Most existing approaches to achieving k-anonymity by clustering are for numerical (or ordinal) attributes. In this paper, we study achieving k-anonymity by clustering in attribute hierarchical structures. We define generalisation distances between tuples to characterise distortions by generalisations and discuss the properties of the distances. We conclude that the generalisation distance is a metric distance. We propose an efficient clustering-based algorithm for k-anonymisation. We experimentally show that the proposed method is more scalable and causes significantly less distortions than an optimal global recoding k-anonymity method. 1
%28alpha
. Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the &#034;shape&#034; of the set. For that purpose, this paper introduces the formal notion of the family of ff-shapes of a finite point set in IR  3  . Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter ff 2 IR controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time O(n  2  ), worst case. A robust implementation of the algorithm is discussed and several applications in the area of scientific computing are mentioned. Categories and Subject Descriptors. F.2.2 [Analysis of Algorithms and Problem Complexity ]: Nonnumerical algorithms and problems --- geometrical problems and computations; G.4 [Mathe-  matics of Computing]: Mathematical Software --- reliability and robustness; I.2.10 [Ar...
Mining top%2DK frequent itemsets from data streams.
E-mail address:
Privacy%2DPreserving Frequent Pattern Mining across Private Databases.
Privacy consideration has much significance in the application of data mining. It is very important that the privacy of individual parties will not be exposed when data mining techniques are applied to a large collection of data about the parties. In many scenarios such as data warehousing or data integration, data from the different parties form a many-to-many schema. This paper addresses the problem of privacy-preserving frequent pattern mining in such a schema across two dimension sites. We assume that sites are not trusted and they are semi-honest. Our method is based on the concept of semi-join and does not involve data encryption which is used in most previous work. Experiments are conducted to study the efficiency of the proposed models. 1
Mining Top%2DK Itemsets over a Sliding Window Based on Zipfian Distribution.

Data Mining for Inventory Item Selection with Cross%2DSelling Considerations.
Abstract. Association rule mining, studied for over ten years in the literature of data mining, aims to help enterprises with sophisticated decision making, but the resulting rules typically cannot be directly applied and require further processing. In this paper, we propose a method for actionable recommendations from itemset analysis and investigate an application of the concepts of association rules- maximalprofit item selection with cross-selling effect (MPIS). This problem is about choosing a subset of items which can give the maximal profit with the consideration of cross-selling effect. A simple approach to this problem is shown to be NP-hard. A new approach is proposed with consideration of the loss rule- a rule similar to the association rule- to model the cross-selling effect. We show that MPIS can be approximated by a quadratic programming problem. We also propose a greedy approach and a genetic algorithm to deal with this problem. Experiments are conducted, which show that our proposed approaches are highly effective and efficient.
Projective Clustering by Histograms.
Abstract — Recent research suggests that clustering for high dimensional data should involve searching for ”hidden ” subspaces with lower dimensionalities, in which patterns can be observed when data objects are projected onto the subspaces. Discovering such inter-attribute correlations and location of the corresponding clusters is known as the projective clustering problem. In this paper, we propose an efficient projective clustering technique by histogram construction (EPCH). The histograms help to generate “signatures”, where a signature corresponds to some region in some subspace, and signatures with a large number of data objects are identified as the regions for subspace clusters. Hence, projected clusters and their corresponding subspaces can be uncovered. Compared to the best previous methods to our knowledge, this approach is more flexible in that less prior knowledge on the data set is required, and it is also much more efficient. Our experiments compare behaviors and performances of this approach and other projective clustering algorithms with different data characteristics. The results show that our technique is scalable to very large databases, and it is able to return accurate clustering result. Index Terms—Projective clustering, histogram, subspace I.
Mining N%2Dmost interesting itemsets without support threshold by the COFI%2Dtree.

ISM Item Selection for Marketing with Cross%2DSelling Considerations.

Real%2DTime Rate Control Via Variable Frame Rate and Quantization Parameters.

MPIS Maximal%2DProfit Item Selection with Cross%2DSelling Considerations.
In the literature of data mining, many different algorithms for association rule mining have been proposed. However, there is relatively little study on how association rules can aid in more specific targets. In this paper, one of the applications for association rules- maximal-profit item selection with cross-selling effect (MPIS) problem- is investigated. The problem is about selecting a subset of items which can give the maximal profit with the consideration of cross-selling. We prove that a simple version of this problem is NP-hard. We propose a new approach to the problem with the consideration of the loss rule- a kind of association rule to model the cross-selling effect. We show that the problem can be transformed to a quadratic programming problem. In case quadratic programming is not applicable, we also propose a heuristic approach. Experiments are conducted to show that both of the proposed methods are highly effective and efficient. 1
